package Z.dailyExercise.April;

import java.util.ArrayList;
import java.util.List;

public class _647回文子串 {
    /**
     * dp[i][j] 从【i，j）的字串是不是
     */

    int res = 0;
    public int countSubstrings(String s) {
        helper(s);
        return res+s.length();

    }
    public void helper(String s){
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;

        }

        for (int l=1;l<n;l++){
            for (int i = 0; i < n-l; i++) {
                int j = i+l;
                if (l == 2){
                    dp[i][j] = s.charAt(i)==s.charAt(j);
                    if (dp[i][j]==true){
                        res++;
                    }
                }else {
                    dp[i][j] = (s.charAt(i)==s.charAt(j)) && dp[i+1][j-1];
                    if (dp[i][j]==true){
                        res++;
                    }
                }

            }
        }

    }

}



